#ifndef __INCLUDED_HIVESTORE_HPP
#define __INCLUDED_HIVESTORE_HPP

#include <memory.h>

template <typename T>
class t_HiveStore
{
protected:

	static const int c_Capacity = 0xFFFF/4;

	struct t_Cell
	{
		T *Target;
		short Unique;
	};

	t_Cell m_Data[c_Capacity];
	short m_NextUnique;
	int m_LastFreeIndex;
	int m_FreeSpace, m_UsedSpace;

	int HandleToIndex(int handle)
	{
		int index = handle & 0xFFFF;
		if(index < 1 || index > c_Capacity)
			return 0;

		int unique = handle >> 16;
		if(unique != m_Data[index].Unique)
			return 0;

		return index;
	}

public:

	t_HiveStore():
		m_NextUnique(1),
		m_LastFreeIndex(1),
		m_FreeSpace(c_Capacity - 1),
		m_UsedSpace()
	{
		memset(m_Data, 0, sizeof(m_Data));
	}

	~t_HiveStore()
	{
		if(!m_UsedSpace)
			return;

		int index = 1;
		while(m_UsedSpace)
		{
			while(!m_Data[index].Target)
				index++;
			delete m_Data[index].Target;
			m_UsedSpace--;
		}
	}

	int Insert(T **item_ptr = nullptr)
	{
		if(!m_FreeSpace)
			throw "Out of space";

		while(m_Data[m_LastFreeIndex].Target) //// NOTE slow!
		{
			m_LastFreeIndex++;
			if(m_LastFreeIndex >= c_Capacity)
				m_LastFreeIndex = 1;
		}
		int index = m_LastFreeIndex;

		T *newitem = new T();
		if(item_ptr)
			*item_ptr = newitem;

		m_Data[index].Target = newitem;
		m_Data[index].Unique = m_NextUnique;

		m_NextUnique++;
		m_FreeSpace--;
		m_UsedSpace++;

		int handle = index | (m_NextUnique << 16);
		return handle;
	}

	bool Remove(int handle)
	{
		int index = HandleToIndex(handle);
		if(!index)
			return false;

		delete m_Data[index].Target;
		m_Data[index].Target = nullptr;
		return true;
	}

	T * operator[](int handle)
	{
		int index = HandleToIndex(handle);
		return index ? m_Data[index].Target : nullptr;
	}

	class t_Iterator
	{
	protected:
		int m_Handle;
	public:
		t_Iterator(int handle): m_Handle(handle) {}
		operator int () const {return m_Handle;}
	};
};

#endif // __INCLUDED_HIVESTORE_HPP